1. Field of the Invention
The present invention generally relates to a dynamic mapping and scheduling apparatus and method. In particular, the present invention relates to such a mapping and scheduling system that may be employed in a computerized and/or networked environment, and employs multiple subsets of weighted path data.
2. Description of Prior Art
Many typical mapping and scheduling systems determine a schedule or time of arrival based upon the lengths of arcs between several points. In this manner, these systems employ data representations of points and paths as nodes and edges. This scheduling is applicable to many different applications, including shipping, delivery routes, airline or other transportation schedules, computer networks, electrical grids, or other natural resource delivery grids.
Typically, a geographic area has many of these nodes and edges. The nodes and edges typically denote, for example, intersections and roads or pathways, respectively. A representation of the intersections and roads or pathways for a particular small or low data density geographic area may be manageable. But when the number of nodes and edges is large, say as in a high density metropolitan area or in a large geographic area, the determination of scheduling and mapping the paths between the points may be an enormous task, due to the large number of possible node-edge computations.
In fact, when mapping an n-point travel matrix, the number of travel values in an optimal routing matrix is n*n (n squared.) This complexity makes the mapping of travel times in large numbers problematic.
Additionally, the load time for these huge problems is also quite large. Building a nodal network linked by weighted paths for a 500,000 node network map is daunting.
Some travel time determinations use coarse solutions, thus decreasing the numbers of nodes and edges. In this case, only major thoroughfares and roads are used in a “fan-out” type computation, and approximations as to specific points are used. This greatly reduces the computational load, as the numbers of edges and nodes are reduced. However, this approximation lends to inherent error in the travel times, since the edges are not completely modeled and since the node locations are only approximated. This is exemplified in travel and transport determinations used in grid-to-grid calculations, which don÷t even use edges or roads. This problem is also typical in systems utilizing scheduling or travel values based on zip code.
In these cases, specific travel times or distances are not determined with the accuracy associated with solutions characterized by highly populated node and edge systems. However, these coarse solutions do offer the ability to encompass solutions for large regions, at the expense of accuracy.
Additionally, these coarse solutions cannot employ explicit path determinations. Nor can they employ bi-directional modes, wherein different travel values can be shown depending on direction of travel. This may be important when dealing in areas having numerous one-way routes.
As such, many typical travel time solutions suffer from deficiencies in providing accurate solutions. Others, using an opposite approach, suffer in computational size and speed for large detailed solutions. Many other problems and disadvantages of the prior art will become apparent to one skilled in the art after comparing such prior art with the present invention as described herein.